package zw_701_800.zw_762_二进制表示中质数个计算置位;

class Solution {

    public static void main(String[] args) {
        int left = 6, right = 10;
        int num = countPrimeSetBits(left, right);
        System.out.println(num);

    }

//    //  i 为 32 位整数，将 `32` 位二进制数分成 `32` 块，每块 `1` 位，`x` 用 `1` 位 存储每块 `1` 的个数
//    x = i
//
//// i 为 32 位整数，将 `32` 位二进制数分成 `16` 块，每块 `2` 位，`x` 用 `2` 位存储每块 `1` 的个数
//// 其中 (x & 0x55555555) 的每块(2位)存储的是整数 i 每块的低 1  位中 1 的个数
//// ((x >>> 1)  & 0x55555555) 的每块(2位)存储的是整数 i 每块的高 1 位中 1 的个数
//            x = (x & 0x55555555) + ((x >>> 1)  & 0x55555555);
//
//// i 为 32 位整数，将 `32` 位二进制数分成 `8` 块，每块 `4` 位，`x` 用 `4` 位存储每块 `1` 的个数
//// 其中 (x & 0x33333333) 的每块(4位)存储的是整数 i 每块的低 2 位中 1 的个数
//// ((x >>> 1)  & 0x55555555) 的每块(4位) 存储的是整数 i 每块中高 2 位中 1 的个数
//    x = (x & 0x33333333) + ((x >>> 2)  & 0x33333333);
//
//// i 为 32 位整数，将 `32` 位二进制数分成 `4` 块，每块 `8` 位，`x` 用 `8` 位存储每块 `1` 的个数
//// 其中 (x & 0x0f0f0f0f) 的每块(8位)存储的是整数 i 每块的低 4 位中 1 的个数
//// ((x >>> 4)  & 0x0f0f0f0f) 的每块(8位) 存储的是整数 i 每块中高 4 位中 1 的个数
//    x = (x & 0x0f0f0f0f) + ((x >>> 4)  & 0x0f0f0f0f);
//
//// i 为 32 位整数，将 `32` 位二进制数分成 `2` 块，每块 `16` 位，`x` 用 `16` 位存储每块 `1` 的个数
//// 其中 (x & 0x00ff00ff) 的每块(16位)存储的是整数 i 每块的低 8 位中 1 的个数
//// ((x >>> 8)  & 0x00ff00ff) 的每块(16位) 存储的是整数 i 每块中高 8 位中 1 的个数
//    x = (x & 0x00ff00ff) + ((x >>> 8)  & 0x00ff00ff);
//
//// i 为 32 位整数，将 `32` 位二进制数分成 `1` 块，每块 `4` 位，`x` 用 `32` 位存储每块 `1` 的个数
//// 其中 (x & 0x0000ffff) 的每块(32位)存储的是整数 i 每块的低 16 位中 1 的个数
//// ((x >>> 16) & 0x0000ffff) 的每块(32位) 存储的是整数 i 每块中高 16 位中 1 的个数
//    x = (x & 0x0000ffff) + ((x >>> 16) & 0x0000ffff);

    /**
     * 模拟 + 分治
     * 枚举 [left,right] 范围内的数总是不可避免，上述解法的复杂度取决于复杂度为 O(logx) 的 lowbit 操作。
     * 采用「分治」思路对二进制进行成组统计，复杂度为 O(loglogx)。
     * https://blog.csdn.net/qq_40950183/article/details/117389310
     */
    static boolean[] hash = new boolean[40];

    static {
        int[] nums = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
        for (int x : nums) hash[x] = true;
    }

    public static int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int i = left; i <= right; i++) {
            int x = i;
            x = (x & 0x55555555) + ((x >>> 1) & 0x55555555);
            x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
            x = (x & 0x0f0f0f0f) + ((x >>> 4) & 0x0f0f0f0f);
            x = (x & 0x00ff00ff) + ((x >>> 8) & 0x00ff00ff);
            x = (x & 0x0000ffff) + ((x >>> 16) & 0x0000ffff);
            if (hash[x]) ans++;
        }
        return ans;
    }


    /**
     * 模拟 + lowbit
     * 利用一个 int 的二进制表示不超过 32，我们可以先将 32 以内的质数进行打表。
     * 从前往后处理 [left,right] 中的每个数 x，利用 lowbit 操作统计 x 共有多少位 1，记为 cnt，若 cnt 为质数，则对答案进行加一操作。
     */
//    static boolean[] hash = new boolean[40];
//    static {
//        int[] nums = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
//        for (int x : nums) hash[x] = true;
//    }
//    public static int countPrimeSetBits(int left, int right) {
//        int ans = 0;
//        for (int i = left; i <= right; i++) {
//            int x = i, cnt = 0;
//            while (x != 0 && ++cnt >= 0) x -= (x & -x);
//            if (hash[cnt]) ans++;
//        }
//        return ans;
//    }


//    public static int countPrimeSetBits(int left, int right) {
//        int ans = 0;
//        for (int i = left; i <= right; i++) {
//            int one = countOne(i);
//            if (isPrime(one)) ans++;
//        }
//        return ans;
//    }
//
//    public static int countOne(int n) {
//        int count = 0;
//        while (n > 0) {
//            count++;
//            n &= (n - 1);
//        }
//        return count;
//    }
//
//    public static boolean isPrime(int n) {
//        if (n == 1) return false;
//        for (int i = 2; i * i <= n; ++i) {
//            if (n % i == 0) {
//                return false;
//            }
//        }
//        return true;
//    }
}